package fun.coding.leetcode;

public class SameTree {

	public static void main(String[] args) {
		
	}

	public boolean isSameTree(TreeNode p, TreeNode q) {
		return isSameTreeHelper(p, q);
	}
	
	private boolean isSameTreeHelper(TreeNode p, TreeNode q) {
		if (p == null && q == null) {
			return true;
		}
		
		if ((p == null && q != null) || (p != null && q == null)) {
			return false;
		}
		
		if (p.val != q.val) {
			return false;
		}
		
		return isSameTreeHelper(p.left, q.left) && isSameTreeHelper(p.right, q.right);
	}
	
	private boolean isSameTreeHelperOptimized(TreeNode p, TreeNode q) {
		if (p == null && q == null) return true;
		if (p == null || q == null) return false; // At this point, as long as one node is null, it is different. 
		
		return p.val == q.val && isSameTreeHelper(p.left, q.left) && isSameTreeHelper(p.right, q.right);
	}
	
}
